package MyBinaryTree;

public class TraversalAlgorithm {
    // 二叉树的遍历算法

    public BiTreeNode searchNode(BiTreeNode t, Object x){
        // 二叉树查找算法 查找一个值在二叉树上的结点
        if(t==null){
            return null;
        }else {
            if(t.data.equals(x)){
                return t;
            }else {
                // 开始使用递归来解决问题
                // 先遍历左子树
                BiTreeNode result = searchNode(t.lchild, x);
                if(result==null){
                    // 左子树遍历完没有了 遍历右子树
                    return searchNode(t.rchild, x);
                }else {
                    return result;
                }
            }
        }
    }


    public int nodeCount(BiTreeNode t){
        // 统计二叉树的结点个数

        int count = 0;
        if(t!=null){
            // 只要结点不为空就计数一次
            count++;
            // 先遍历玩左子树
            count = count + nodeCount(t.lchild);
            // 在遍历右子树
            count = count + nodeCount(t.rchild);
        }
        return count;
    }

    public int getDepth(BiTreeNode t){
        // 求二叉树的深度


        if(t==null){
            return 0;
        }else {
            // 递归遍历左子树
            int ldepth = getDepth(t.lchild);
            // 递归遍历右子树
            int rdepth = getDepth(t.rchild);

            // 左右子树比较 最后谁大谁+1（深度=递归次数 + 根节点(1个) ）
            if(ldepth < rdepth){
                return rdepth + 1;
            }else {
                return ldepth + 1;
            }
        }
    }

}
